package com.huawei.tree;

import com.huawei.common.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;


/**
 * @Author admin
 * @Description 二叉树的层序遍历
 * @Date 2023/11/12/9:48
 * @Version 1.0
 */
public class SequenceTraversalOfBinaryTree {


	public static void main(String[] args) {
		TreeNode root = new TreeNode(1);
		root.left = new TreeNode(2);
		root.right = new TreeNode(3);
		root.right.left = new TreeNode(4);
		root.right.right = new TreeNode(5);
		System.out.println(SequenceTraversalOfBinaryTree.levelOrder(root));
	}

	/**
	 * BFS - 二叉树的层次遍历
	 * 使用LinkedList来模拟队列
	 * @param root
	 * @return
	 */
	public static List<List<Integer>> levelOrder(TreeNode root) {
		Queue<TreeNode> queue = new LinkedList<>();
		List<List<Integer>> res = new ArrayList<>();
		if (root != null) queue.add(root);
		while (!queue.isEmpty()) {
			List<Integer> tmp = new ArrayList<>();
			for (int i = queue.size(); i > 0; i--) {
				// 删除队列的头部元素
				TreeNode node = queue.poll();
				tmp.add(node.val);
				// 把左右子节点加入队列
				if (node.left != null) queue.add(node.left);
				if (node.right != null) queue.add(node.right);
			}
			res.add(tmp);
		}
		return res;

	}
}
